package com.mid;

/**
 * Created by Lxk on 2020/2/15.
 */
class Trie {

    private static class Node {

        private char ch;

        private Node[] child;

        private boolean isEnd;

        public Node(char ch) {
            this.ch = ch;
        }

        public Node(char ch, boolean isEnd) {
            this.ch = ch;
            this.isEnd = isEnd;
        }
    }

    private Node[] root;

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        this.root = new Node[26];
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        Node[] curArr = root;
        Node preNode = null;
        for (int pos = 0; pos < word.length(); pos++) {
            if (pos >= word.length()) {
                return;
            }
            if (curArr == null) {
                curArr = new Node[26];
                preNode.child = curArr;
            }
            //该字符位置为空
            if (curArr[word.charAt(pos) - 'a'] == null) {
                Node cur = new Node(word.charAt(pos));
                if (pos == word.length() - 1) {
                    cur.isEnd = true;
                }
                curArr[word.charAt(pos) - 'a'] = cur;
            } else {
                if (pos == word.length() - 1) {
                    curArr[word.charAt(pos) - 'a'].isEnd = true;
                }
            }

            preNode = curArr[word.charAt(pos) - 'a'];
            curArr = preNode.child;
        }
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        Node[] cur = root;
        for (int pos = 0; pos < word.length(); pos++) {
            if (cur != null && cur[word.charAt(pos) - 'a'] != null) {
                if (pos != word.length() - 1) {
                    cur = cur[word.charAt(pos) - 'a'].child;
                } else {
                    return cur[word.charAt(pos) - 'a'].isEnd;
                }
            } else {
                return false;
            }
        }
        return true;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        Node[] cur = root;
        for (int pos = 0; pos < prefix.length(); pos++) {
            if (cur != null && cur[prefix.charAt(pos) - 'a'] != null) {
                cur = cur[prefix.charAt(pos) - 'a'].child;
            } else {
                return false;
            }
        }
        return true;
    }
}

public class Solution208 {

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("app");
        trie.insert("apple");
        trie.insert("beer");
        trie.insert("add");
        trie.insert("jam");
        trie.insert("rental");
        System.out.println(trie.search("apps"));
        System.out.println(trie.search("app"));
    }

}
